class Solution:
    def longestRepeatingSubstring(self, s: str) -> int:
        size = len(s)
        left, right = 0, size - 1

        while left < right:
            mid = (left + right) // 2 + 1

            find = False
            temp = set()
            for i in range(size - mid + 1):
                if s[i:i + mid] in temp:
                    find = True
                    break
                else:
                    temp.add(s[i:i + mid])

            if find:
                left = mid
            else:
                right = mid - 1

        return left


if __name__ == "__main__":
    print(Solution().longestRepeatingSubstring("abcd"))  # 0
    print(Solution().longestRepeatingSubstring("abbaba"))  # 2
    print(Solution().longestRepeatingSubstring("aabcaabdaab"))  # 3
    print(Solution().longestRepeatingSubstring("aaaaa"))  # 4
